#pragma once 
#include <iostream>

template <class T>
class ListNode
{
public:
	ListNode<T>* _next;
	T _data;
	ListNode(T data =  T())
		:_data(data), _next(nullptr)
	{}
};

template <class T>
class SList
{
public:
	SList()
		:phead(new ListNode<T>())
	{}
	~SList()
	{
		while (phead)
		{
			ListNode<T>* next = phead->_next;
			delete phead;
			phead = next;
		}
	}

	ListNode<T>* Find(T x)
	{
		ListNode<T>* cur = phead->next;
		while (cur)
		{
			if (cur->_data == x)
				return cur;
		}
		return nullptr;
	}

	void Print()
	{
		ListNode<T>* cur = phead->_next;
		while (cur)
		{
			std::cout << cur->_data << " ";
			cur = cur->_next;
		}
		std::cout << std::endl;
	}
public:
	void Pushback(T x)
	{
		ListNode<T>* prev = phead;
		while (prev->_next)
		{
			prev = prev->_next;
		}
		prev->_next = new ListNode<T>(x);
	}

	void Popback()
	{
		ListNode<T>* prev = phead;
		if (prev->_next) return;
		else
		{
			while (prev->_next)
				prev = prev->_next;
			delete prev->_next;
			prev->_next = nullptr;
		}
	}

	void Pushfront(T x)
	{
		ListNode<T>* next = phead->_next;
		ListNode<T>* cur = new ListNode<T>(x);
		phead->_next = cur;
		cur->_next = next;
	}

	void Popfront()
	{
		if (phead->_next == nullptr) return;
		else
		{
			ListNode<T>* next = phead->_next;
			phead->_next = next->_next;
			delete next;
		}
	}
private:
	ListNode<T>* phead;
};